package com.kevinkk.hashmap;

import java.util.*;

/**
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * <p>
 * 这道题是 哈希表 和 滑动窗口的结合
 * 但是需要注意的是，这个滑动窗口的大小是固定的，根据字母异位词的定义滑动窗口的大小肯定是等雨 p 的长度
 */

public class FindAllAnagramsInAString {
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            char[] sc = s.toCharArray(), pc = p.toCharArray();
            int[] sCount = new int[26], pCount = new int[26];
            int slen = sc.length, plen = pc.length;
            if (slen < plen)
                return res;

            for (char c : pc)
                pCount[c - 'a']++;
            for (int i = 0; i < plen; i++)
                sCount[sc[i] - 'a']++;

            if (Arrays.equals(pCount, sCount))
                res.add(0);
            for (int i = plen; i < slen; i++) {
                // 窗口的大小固定，左边移动 右边也要跟着移动
                sCount[sc[i - plen] - 'a']--;
                sCount[sc[i] - 'a']++;
                if (Arrays.equals(pCount, sCount))
                    res.add(i - plen + 1);
            }
            return res;
        }
    }
}
